package symbolTable.primaryST;

import stackAndQueue.Stack;

public class BinarySearchST<Key extends Comparable<Key>, Value> {
    private Key[] keys;
    private Value[] values;
    private int N;

    public BinarySearchST() {
        keys = (Key[]) new Comparable[1];
        values = (Value[]) new Object[1];
    }

    private void resize(int maxSize) {
        Key[] tempKeys = (Key[]) new Comparable[maxSize];
        Value[] tempValues = (Value[]) new Object[maxSize];
        for (int i = 0; i < N; i++) {
            tempKeys[i] = keys[i];
            tempValues[i] = values[i];
        }
        keys = tempKeys;
        values = tempValues;
    }

    public int size() {
        return N;
    }

    public boolean isEmpty() {
        return N == 0;
    }

    public int rank(Key key) {
        int lo = 0;
        int hi = N - 1;
        while (lo <= hi) {
            int mid = (lo + hi) / 2;
            int cmp = key.compareTo(keys[mid]);
            if (cmp < 0) hi = mid - 1;
            else if (cmp > 0) lo = mid + 1;
            else return mid;
        }
        return lo;
    }

    public Value get(Key key) {
        int i = rank(key);
        if (i < N && keys[i].compareTo(key) == 0)
            return values[i];
        return null;
    }

    public void put(Key key, Value value) {
        int i = rank(key);
        if (i < N && keys[i].compareTo(key) == 0) {
            values[i] = value;
            return;
        }
        for (int j = N; j > i; j--) {
            keys[j] = keys[j - 1];
            values[j] = values[j - 1];
        }
        keys[i] = key;
        values[i] = value;
        N++;
        if (N == keys.length)
            resize(2 * N);
    }

    public void delete(Key key) {
        int i = rank(key);
        if (i < N && keys[i].compareTo(key) == 0) {
            for (int j = i; j < N - 1; j++) {
                keys[j] = keys[j + 1];
                values[j] = values[j + 1];
            }
            keys[N - 1] = null;
            values[N - 1] = null;
            N--;
            if (N == keys.length / 4)
                resize(keys.length / 2);
        } else
            System.out.println("要删除的键不存在");
    }
    public Iterable<Key> keys(){
        Stack<Key> stack = new Stack<>();
        for (int i=0;i<N;i++)
            stack.push(keys[i]);
        return stack;
    }
}
